This specification generally relates to search engines, and one particular implementation relates to evaluating optionalization rules that are used in revising search queries.